package com.yinxin.wudasuanfa.huaweiod;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author yinxin
 * @version 1.0
 * @Description: 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，
 * 从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，
 * 如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，
 * 当然密码学会希望你寻找出“最佳方案”。
 * @date 2022/5/139:02
 */
public class Exercise12Hard {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long[] arr =new long[N];
        for (int i = 0; i < N; i++) {
            arr[i]=sc.nextLong();
        }
        System.out.println(Arrays.toString(arr));
        // 偶数部分
        ArrayList<Long> evens = new ArrayList<Long>();
        // 奇数部分
        ArrayList<Long> odds = new ArrayList<Long>();
        for (int i = 0; i < N; i++) {
            if(arr[i]%2==0){
                evens.add(arr[i]);
            }else {
                odds.add(arr[i]);
            }
        }
        // 和偶数同样长度的数组，索引位对应的events中的偶数，和其值为一对素数
        long[] evensMatch = new long[evens.size()];
        int result = 0;
        for (Long odd : odds) {
            int[] used = new int[evens.size()];
            if (find(odd, evens, used, evensMatch)) {
                result++;
            }
        }
        System.out.println(result);
    }

    /**
     *
     * @param x 奇数中的一个
     * @param evens 偶数列表
     * @param used 偶数对应索引位上的数被组合成素数后，used数组对应索引变成1否则为0
     * @param evensMatch 和偶数同样长度的数组，索引位对应的events中的偶数，和其值为一对素数
     * @return
     */
    public static boolean find(long x, ArrayList<Long> evens, int[] used, long[] evensMatch) {
        int j;
        for (j = 0; j < evens.size(); j++) {
            if (isPrime(x + evens.get(j)) && used[j] == 0) {
                used[j] = 1;
                if (evensMatch[j] == 0 || find(evensMatch[j], evens, used, evensMatch)) {
                    evensMatch[j] = x;
                    return true;
                }
            }
        }
        return false;
    }


    //判断数组中两数之和是否为质数
    private static boolean isPrime(long num) {
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
            if (num == 1) {
                return false;
            }
        }
        return true;
    }

}
